import collections


class Solution(object):
    def generatePalindromes(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        if len(s) == 1:
            return [s]
        d = collections.Counter(s)
        count = 0
        c = s[0]
        for key in d:
            if d[key] % 2 == 1:
                count += 1
                c = key
            d[key] = d[key] // 2
        if count >= 2:
            return []

        def search():
            now_out = []
            for key in d:
                if d[key] > 0:
                    d[key] -= 1
                    next_out = search()
                    if not next_out:
                        now_out.append(key)
                    else:
                        for item in next_out:
                            now_out.append(key + item)
                    d[key] += 1
            return now_out

        out = search()
        if count == 1:
            for i, item in enumerate(out):
                out[i] = out[i] + c + item[::-1]
        else:
            for i, item in enumerate(out):
                out[i] = out[i] + item[::-1]
        return out


data = Solution()
s = "a"
print(data.generatePalindromes(s))
